package com.summer.study.leetcode.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @auther: 杨杰
 * @date: 2019/7/31 16:34
 * @description: 三角形最小路径和
 * https://leetcode-cn.com/problems/triangle/
 */
public class Demo120 {

    private static List<List<Integer>> triangle() {

        return Arrays.asList(
                Arrays.asList(-1),
                Arrays.asList(2, 3),
                Arrays.asList(1, -1, -3));
        /*
        return Arrays.asList(
                Arrays.asList(2),
                Arrays.asList(3, 4),
                Arrays.asList(6, 5, 7),
                Arrays.asList(4, 1, 8, 3));*/
    }


    public static int minimumTotal(List<List<Integer>> triangle) {
        int num = 0;
        for (int i = 0; i < triangle.size(); i++) {
            List<Integer> innerList = triangle.get(i);
            int innerNum = Integer.MAX_VALUE;
            for (int j = (i-1<0?0:i-1); j < i+1; j++) {
                int cuurent = innerList.get(j);
                if (cuurent < innerNum) {
                    innerNum = cuurent;
                }
            }
            System.out.println("第"+i+"层最小的数为："+innerNum);
            num += innerNum;
        }
        return num;
    }

    public static void main(String[] args) {
        System.out.println(minimumTotal(triangle()));
    }

}
